package com.zklh.leetcode.top100;

import com.zklh.leetcode.tree.model.TreeNode;

/**
 * 二叉树最近公共祖先
 *
 * @version 1.0
 * @Author tongnan
 * @Date 2023/10/8
 */
public class Solution236 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }

        if (root.val == p.val || root.val == q.val) {
            return root;
        }

        TreeNode leftNode = lowestCommonAncestor(root.left, p, q);

        TreeNode rightNode = lowestCommonAncestor(root.right, p, q);

        if (leftNode != null && rightNode != null) {
            return root;
        }

        if (leftNode != null || rightNode != null) {
            return leftNode != null ? leftNode : rightNode;
        }

        return null;

    }
}